#include <iostream>
#include <gmp.h>
#include <string>
#include <ctime>
#include <list>

using namespace std;
//
// Compile with g++ test.cpp -o test -lgmp
// segmentation fault in main()
// between the output "3" and "4"
//

static long endTime; 
static long finishTime;
static mpz_t NEG_ONE;
static mpz_t ONE;
static mpz_t TWO;
static mpz_t THREE;
static mpz_t FIVE;
static mpz_t SEVEN;
static mpz_t ELEVEN;
gmp_randstate_t STATE;

void f(mpz_t x, mpz_t c, mpz_t n)
{
	mpz_mul(x, x, x);
	mpz_sub(x,x,c);
	mpz_mod(x,x,n);
}

void pollardRho(mpz_t d, mpz_t n)
{
	mpz_t temp;
	mpz_mod(temp,n,TWO);
	if (mpz_cmp(temp,ONE)==0){
		d = TWO;
		return;
	}
	mpz_mod(temp,n,THREE);
	if (mpz_cmp(temp,ONE)==0){
		d = THREE;
		return;
	}
	mpz_mod(temp,n,FIVE);
	if (mpz_cmp(temp,ONE)==0){
		d = FIVE;
		return;
	}
	mpz_mod(temp,n,SEVEN);
	if (mpz_cmp(temp,ONE)==0){
		d = SEVEN;
		return;
	}
	mpz_mod(temp,n,ELEVEN);
	if (mpz_cmp(temp,ONE)==0){
		d = ELEVEN;
		return;
	}
	
	mpz_t x;
	mpz_t y;
	
	mpz_urandomm (x, STATE, n);
	mpz_init_set(y,x);
	mpz_set(d,ONE);
	while(mpz_cmp(d,ONE)==0){
		if(time(0)>endTime){
			d = NEG_ONE;
			return;
		}
		f(x,ONE,n);
		f(y,ONE,n);
		f(y,ONE,n);
		mpz_sub(d,x,y);
		mpz_gcd (d,d,n);
	}
	return;
}

int getfactors(mpz_t n, list<string> ll ,bool firstInput)
{
	if (mpz_cmp(n,ONE)==0){
		return 1;
	}
	if(mpz_probab_prime_p(n,20)){
		char* str = new char;
		str = mpz_get_str (str, 10, n);
		ll.push_back(string(str));
		return 1;
	}
	mpz_t f1;
	mpz_t f2;
	pollardRho(f1,n);
	mpz_divexact (f2, n, f1);
	if(getfactors(f1,ll, false)==-1){
		return -1;
	}
	if(getfactors(f2,ll, false)){
		return -1;
	}
	return 1;
}
 
int main(int argc, char *argv[])
{
	mpz_init_set_str (NEG_ONE, "-1", 10);
	mpz_init_set_str (ONE, "1", 10);
	mpz_init_set_str (TWO, "2", 10);
	mpz_init_set_str (THREE, "3", 10);
	mpz_init_set_str (FIVE, "5", 10);
	mpz_init_set_str (SEVEN, "7", 10);
	mpz_init_set_str (ELEVEN, "11", 10);
	gmp_randinit_default (STATE);

	cout << "1";

	long finishTime = time(0) + 15000;
	int i = 0;
	while(cin){
		cout << "2";
		long current = time(0);
		long time = (finishTime - current)/(100-i);
		endTime = current+time;
		mpz_t n;
		string input;
		cout << "3";
		getline(cin,input);	// Här blir det seqmentation fault
		cout << "4";
		const char *p;
		p=input.c_str();
		mpz_init_set_str (n, p, 10);
		list<string> ll;
		cout << "5";
		int i = getfactors(n,ll, true);
		if(i==-1){
			cout << "fail" << endl;
		} else {
			list<string>::iterator s;
			for(s=ll.begin(); s != ll.end(); ++s){
				cout << *s << endl;
			}
		}
		cout << endl;
		i++;
	}
}


//int main(int argc, char *argv[])
//{
 // mpz_t a, b;                 		/* working numbers */
//  if (argc<3)
//    {					/* not enough words */
//    printf("Please supply two numbers to add.\n");
//    return 1;
//  }
//  mpz_init_set_str (a, argv[1], 10);	/* Assume decimal integers */
//  mpz_init_set_str (b, argv[2], 10);	/* Assume decimal integers */
//  mpz_add (a, a, b);			/* a=a+b */
//
//  printf("%s + %s => %s\n", argv[1], argv[2], mpz_get_str (NULL, 10, a));
//  return 0;
//}
